Conventional wired communications networks, such as, for example, the Internet, use various algorithms for disseminating routing data necessary for routing packets from a source node to a destination node. Each node of the network that handles packets has sufficient knowledge of the network topology such that it can choose the right output interface through which to forward received packets. Link state routing algorithms, such as the OSPF algorithm, permit the construction of a network topology such that any given node in the network may make packet-forwarding decisions. OSPF is defined by Internet RFC 2328, STD 54, and related documents, published by the Internet Society. OSPF is also defined by Internet RFC 2740, and related documents, also published by the Internet Society.
OSPF has conventionally been implemented in wired point-to-point or multi-access (Ethernet like) networks. It may also be highly desirable to implement OSPF over a multi-hop, multi-access packet radio network with its own private, internal routing system, so as to permit seamless integration of such a network into an OSPF environment, and to achieve strict compatibility between that packet radio network and standard COTS (Commercial Off-The-Shelf) routers outside that network. This can be achieved either by implementing OSPF at a higher layer over the multi-hop, multi-access packet radio network on top of that network's private, internal routing system, or by implementing both routing systems in parallel at the same network layer. In such a scheme, OSPF would be responsible for routing between the packet radio network and external hosts or networks, while the packet radio network's internal routing system would handle routing of packets within the network. Similar schemes are commonly used to implement OSPF over, for example, an X.25 packet switched network or an ATM packet network, and are well-known to practitioners of the art.
However, a number of difficulties may arise if OSPF is implemented over a multi-hop, multi-access packet radio network with its own private, internal routing system. Although the private, internal routing system of such a network may enable it to appear to OSPF much like a wired network, the properties and characteristics of such radio networks are nevertheless very different from those of wired point-to-point or multi-access networks. Like an Ethernet, such radio networks link together a large number of routers; and also like an Ethernet, such networks typically provide a suite of unicast, multicast, and netwide broadcast services. However, unlike an Ethernet, such networks possess internal structure of their own. Both unicast and multicast packets may need to be relayed across the network by multiple lower-layer hops in accordance with the network's private routing scheme, and replicated many times in the process. Consequently, the cost of transport across the network is not the same for every node, but instead depends upon the location of the entrance and exit point. The traffic load on such a network may, therefore, depend just as critically upon appropriate choices of entrance and exit point, as upon efficient routing within the network.
Even worse, the structure of the radio network may fluctuate and, hence, these costs may be constantly changing due to radio mobility, interference, fading, and other causes. Furthermore, the capacity and reliability of such networks is typically much lower than for an Ethernet, and delays much longer; capacity is limited by the available radio bandwidth, reliability is reduced by increased risks of collisions, interface, noise, and fading, and by the possibility of transient routing inconsistencies at the lower layer; and delay is increased by the multi-hop relaying at the intranet layer.
Furthermore, the need to replicate packets within such a network for either unicast or multicast forwarding may introduce or exacerbate problems involved in scaling to networks with large numbers of nodes, especially large numbers of OSPF routers. This is especially unfortunate, as certain applications may require thousands of OSPF routers on such a network.
Therefore, there exists a need for systems and methods that can resolve some of the inherent problems that exist with implementing OSPF in a multi-hop, multi-access packet radio network.